Search results for " Turin"
showing 10 items of 26 documents
Hartmanis-Stearns Conjecture on Real Time and Transcendence
2012
Hartmanis-Stearns conjecture asserts that any number whose decimal expansion can be computed by a multitape Turing machine is either rational or transcendental. After half a century of active research by computer scientists and mathematicians the problem is still open but much more interesting than in 1965.
Positive Versions of Polynomial Time
1998
Abstract We show that restricting a number of characterizations of the complexity class P to be positive (in natural ways) results in the same class of (monotone) problems, which we denote by posP . By a well-known result of Razborov, posP is a proper subclass of the class of monotone problems in P . We exhibit complete problems for posP via weak logical reductions, as we do for other logically defined classes of problems. Our work is a continuation of research undertaken by Grigni and Sipser, and subsequently Stewart; indeed, we introduce the notion of a positive deterministic Turing machine and consequently solve a problem posed by Grigni and Sipser.
Social rights of young people: The role of local and regional authorities
2020
En el marco de toda una serie de debates, resoluciones y otros instrumentos tendentes a fortalecer la integración, participación y compromiso de la juventud a nivel local y regional, este artículo pone el acento en los derechos sociales de los jóvenes garantizados por la Carta Social Europea. Subraya el papel esencial de los entes locales y regionales, en virtud de sus competencias en el ámbito social, para facilitar el acceso y el ejercicio efectivo de los derechos sociales por parte de los jóvenes; a tal efecto, se pone el énfasis en el cumplimiento de la Carta Social y su jurisprudencia como fuentes de inspiración para la acción local y regional en este terreno. El artículo hace un llama…
One-Counter Verifiers for Decidable Languages
2013
Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS’s for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca’s). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be spac…
Cross-diffusion effects on stationary pattern formation in the FitzHugh-Nagumo model
2022
<p style='text-indent:20px;'>We investigate the formation of stationary patterns in the FitzHugh-Nagumo reaction-diffusion system with linear cross-diffusion terms. We focus our analysis on the effects of cross-diffusion on the Turing mechanism. Linear stability analysis indicates that positive values of the inhibitor cross-diffusion enlarge the region in the parameter space where a Turing instability is excited. A sufficiently large cross-diffusion coefficient of the inhibitor removes the requirement imposed by the classical Turing mechanism that the inhibitor must diffuse faster than the activator. In an extended region of the parameter space a new phenomenon occurs, namely the exis…
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines
1999
The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this class if and only if there is a formula of the form ∃f1..∃fk∃R1..∃Rm∀xφv; that is true exactly for all strings in L. In this formula the fi are unary function symbols, the Ri are unary relation symbols and φv; is a quantifierfree formula. Furthermore, the quantification of functions is restricted to non-crossing, decreasing functions and in φv; no equations in which different functions occur are allowed. There are a number of variations of this statement, e.g., it holds also for k = 3. From these r…
Minimal nontrivial space complexity of probabilistic one- way turing machines
2005
Languages recognizable in o(log log n) space by probabilistic one — way Turing machines are proved to be regular. This solves an open problem in [4].
Two Democracies Work Better Together. French and Italian decision-making processes for the Turin-Lyon railway project.
2013
The Pan-European Corridor V railway line connects Lisbon and Kiev and touches many European countries. The paper present focuses on the Turin-Lyon section where French and Italian authorities jointly work on this huge infrastructure project while applying different approaches. While there are provisions for a public debates on such issues in France, there is no similar institutional framework in Italy. Hence, the analysis allows to compare the dynamics of the public debate in two democratic systems with different public decision-making systems and political cultures. While the French case evidences that public institutions can activate participation by providing “invited spaces” for collect…
Quantum Computation With Devices Whose Contents Are Never Read
2010
In classical computation, a "write-only memory" (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic or probabilistic) classical computer brings no advantage. We prove that quantum computers that are augmented with WOM can solve problems that neither a classical computer with WOM nor a quantum computer without WOM can solve, when all other resource bounds are equal. We focus on realtime quantum finite automata, and examine the increase in their power effected by the addition of WOMs with different access modes and capacities. Some problems that are unsolvable by two-way probabilistic Turing machines using sublogarithmic amounts of read/write memory are shown to…
Turing Instability and Pattern Formation for the Lengyel–Epstein System with Nonlinear Diffusion
2014
In this work we study the effect of density dependent nonlinear diffusion on pattern formation in the Lengyel---Epstein system. Via the linear stability analysis we determine both the Turing and the Hopf instability boundaries and we show how nonlinear diffusion intensifies the tendency to pattern formation; in particular, unlike the case of classical linear diffusion, the Turing instability can occur even when diffusion of the inhibitor is significantly slower than activator's one. In the Turing pattern region we perform the WNL multiple scales analysis to derive the equations for the amplitude of the stationary pattern, both in the supercritical and in the subcritical case. Moreover, we c…